package com.example.demo.service;

import org.springframework.stereotype.Component;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@Component
public class SudokuSolution {//求解9×9的数独，每个小正方形为3×3
    private static final int n = 3, N = 9;
    private static final ThreadLocal<Boolean[][]> local1 = new ThreadLocal<>();
    private static final ThreadLocal<Boolean[][]> local2 = new ThreadLocal<>();
    private static final ThreadLocal<Boolean[][][]> local3 = new ThreadLocal<>();
    private static final ThreadLocal<Boolean> validLocal = new ThreadLocal<>();

    public void solveSudoku(char[][] board) {
        validLocal.set(false);
        Boolean[][] set1 = new Boolean[N][N];
        Boolean[][] set2 = new Boolean[N][N];
        Boolean[][][] set3 = new Boolean[n][n][N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(set1[i], false);
            Arrays.fill(set2[i], false);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(set3[i][j], false);
            }
        }
        local1.set(set1);
        local2.set(set2);
        local3.set(set3);

        List<int[]> list1 = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == '.') {//点号表示空格，需要用户填入数字
                    list1.add(new int[]{i, j});
                } else {
                    int num = board[i][j] - '1';
                    set1[i][num] = true;
                    set2[j][num] = true;
                    set3[i/n][j/n][num] = true;

                    local1.set(set1);
                    local2.set(set2);
                    local3.set(set3);
                }
            }
        }
        backtrack(board, 0, list1);
    }

    private void backtrack(char[][] board, int pos, List<int[]> list1) {
        if (pos == list1.size()) {
            validLocal.set(true);
            return;
        }
        int[] arr = list1.get(pos);
        int i = arr[0], j = arr[1];
        for (int k = 0; k < N && !validLocal.get(); k++) {
            Boolean[][] set1 = local1.get();
            Boolean[][] set2 = local2.get();
            Boolean[][][] set3 = local3.get();

            if (!set1[i][k] && !set2[j][k] && !set3[i/3][j/3][k]) {
                set1[i][k] = set2[j][k] = set3[i/3][j/3][k] = true;
                board[i][j] = (char) ('1' + k);
                backtrack(board, pos + 1, list1);
                set1[i][k] = set2[j][k] = set3[i/3][j/3][k] = false;
            }
        }
    }
}
